package 数据结构.LinkList.diamond;

//设计双向链表
public class MyLinkedList {
    int size;
    ListNode head;
    ListNode tail;

    public MyLinkedList() {
        size = 0;

    }

    class ListNode {
        int val;
        ListNode next;
        ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }
    }

    //获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
    public int get(int index) {
        ListNode head = this.head;
        //todo：有问题
        for (int i = 0; i <index; i++) {
            if (head != null && head.next != null) {
                head = head.next;
            } else {
                return -1;
            }
        }
        return head.val;
    }

    //将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
    public void addAtHead(int val) {

        ListNode head = new ListNode(val);
        if (this.head == null) {
            this.head = head;
            this.size++;
            return;
        }
        ListNode oldHead = this.head;
        head.next = oldHead;
        oldHead.prev = head;
        head.prev = null;
        this.head = head;
        this.size++;
    }

    //将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
    public void addAtTail(int val) {
        ListNode tail = new ListNode(val);
        ListNode head = this.head;
        //得到此时的尾节点
        while (head != null && head.next != null) {
            head = head.next;
        }
        //todo：报黄的都得改：
        //如果此时的head为null呢
        if (head == null) {
            this.head = tail;
            this.size++;
            return;
        }
        head.next = tail;
        tail.prev = head;
        this.size++;
    }

    //将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，
    // 那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
    public void addAtIndex(int index, int val) {
        ListNode tem = new ListNode(val);
        ListNode head = this.head;
        //得到当前节点
        int size = 0;
        //
        for (int i = 0; i < index; i++) {
            if (head != null && head.next != null) {
                head = head.next;
            }
            size++;
            //
        }
        if (this.head == null) {
            this.head = tem;
            this.size++;
            return;
        }

        if (index == this.size) {
            //判断0的情况：
            tem.prev = head;
            //只有一个的情况,head只有一个
            //
            head.next = tem;
            tem.next = null;
            return;
        }
        //插入到这个节点之前，如果执行到这里 证明不是要插到尾节点 而是要插入到xx之前
        //那如果此时的head
        ListNode old_prev = head.prev;
        head.prev = tem;
        //ole_prev有可能为空
        if(old_prev==null){
            //证明插入的是头节点位置
            tem.next=head;
            this.head=tem;
            return;
        }
        old_prev.next = tem;
        tem.prev = old_prev;
        tem.next = head;
        return;
    }


    //如果下标有效，则删除链表中下标为 index 的节点。
    public void deleteAtIndex(int index) {
        ListNode head = this.head;
        for (int i = 0; i < index; i++) {
            if (head != null && head.next != null) {
                head = head.next;
            }
        }
        //如果头节点为空，则代表着不可能删掉
        if (this.head == null) {
            return;
        }
        ListNode prev = head.prev;

        ListNode next = head.next;

        //有可能头节点，
        if (prev == null) {
            //证明要删除的是头节点
            this.head = next;//这个有可能为空，即next为null 只有一个节点在链表中
            if(next==null){
                return;
            }
            next.prev = null;
            return;
        }
        //有可能为尾节点
        if (next == null) {
            prev.next = null;
            return;
        }
        prev.next = next;
        next.prev = prev;
    }

    public void printList() {
        ListNode current = this.head;
        while (current != null) {
            System.out.print(current.val + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        MyLinkedList obj = new MyLinkedList();
//        int param_1 = obj.get(1);
//        System.out.println(param_1);
        obj.addAtHead(2);
        obj.printList();
        obj.deleteAtIndex(1);
        obj.printList();
        obj.addAtHead(2);
        obj.printList();
        obj.addAtHead(7);
        obj.printList();
        obj.addAtHead(3);
        obj.printList();
        obj.addAtHead(2);
        obj.printList();
        obj.addAtHead(5);
        obj.printList();
        obj.addAtTail(5);
        obj.printList();
        System.out.println(obj.get(5));
        obj.printList();

        obj.deleteAtIndex(6);obj.deleteAtIndex(4);
        obj.printList();
 /*       obj.addAtIndex(1, 2);
        obj.addAtIndex(1, 2);*/
        obj.printList();

        obj.printList();
    }
}
